package kyssion.leetcode.num1_50;

import java.util.*;

/**
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * <p>
 * 满足要求的三元组集合为：
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 */

/**
 * 这里对数组这种问题做一下总结把,其实对数组的操作无非几种情况,
 * 1. 排序
 * 2. 栈队列
 * 3. 双指针
 * 4. 缓存
 * 5. 下标
 * 6. 二分
 */
public class code15_三数之和 {
    public static void main(String[] args) {
        System.out.println(new code15_三数之和().threeSum(new int[]{
                0, 0, 0, 0, 0, 0
        }));
    }

    /**
     * 简单暴力方法,超时三层循环会超时
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for (int a = 0; a < nums.length; a++) {
            if (a > 0 && nums[a - 1] == nums[a]) {
                continue;
            }
            for (int b = a + 1; b < nums.length; b++) {
                if (b > a + 1 && nums[b - 1] == nums[b]) {
                    continue;
                }
                for (int c = b + 1; c < nums.length; c++) {
                    if (c > b + 1 && nums[c - 1] == nums[c]) {
                        continue;
                    }
                    if (nums[a] + nums[b] + nums[c] == 0) {
                        List<Integer> item = new ArrayList<>();
                        item.add(nums[a]);
                        item.add(nums[b]);
                        item.add(nums[c]);
                        lists.add(item);
                    }
                }
            }
        }
        return lists;
    }

    /**
     * 通过这种方法优化到了n^2 复杂度
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);

        HashMap<Integer, Integer> number =
                new HashMap<>();
        for (int a = 0; a < nums.length; a++) {
            number.put(nums[a], a);
        }

        for (int a = 0; a < nums.length; a++) {
            if (a > 0 && nums[a - 1] == nums[a]) {
                continue;
            }
            for (int b = a + 1; b < nums.length; b++) {
                if (b > a + 1 && nums[b - 1] == nums[b]) {
                    continue;
                }
                if (number.containsKey(-(nums[a] + nums[b])) && number.get(-(nums[a] + nums[b])) > b) {
                    List<Integer> item = new ArrayList<>();
                    item.add(nums[a]);
                    item.add(nums[b]);
                    item.add(0 - nums[a] - nums[b]);
                    lists.add(item);
                }
            }
        }
        return lists;
    }


    /**
     *  hashmap计数法
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum3(int[] nums) {
        if(nums == null){
            return null;
        }
        if(nums.length < 3){
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        HashSet<List<Integer>> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k){
                if(nums[i] + nums[j] + nums[k] == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    set.add(list);
                    while(j < k && nums[j] == nums[j + 1]){
                        j++;
                    }
                    while(j < k && nums[k] == nums[k - 1]){
                        k--;
                    }
                    j++;
                    k--;
                }else if(nums[i] + nums[j] + nums[k] < 0){
                    j++;
                }else{
                    k--;
                }
            }
        }
        return new ArrayList<>(set);
    }

    /**
     * 进行 0 值优化
     * 这里就不写代码了,说一下思路
     * 将数组拆分成比0大的和比0 小的
     * 接下来使用上面的逻辑,负数是1个的情况下和两个情况下分别套路
     * 原始的负载度是n^2
     * 这种优化可以将复杂度降低一半,并且在匹配的时候还可以充分的利用有序的状态,进行更加牛逼的优化
     * 比如如果负数是100 如果两个值相加之后导致最小的值已经变化了,这个值就很难受了
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum4(int[] nums) {
        return new ArrayList<>();
    }
}
